package TransportProblem;

import java.util.HashMap;
import java.util.Map;

public class SolutionGenerater {

	private Route emptyRoute;
	private boolean[] choosen;

	public SolutionGenerater() {
		// todo
	}

	public void initialSolution_cheapestVersion(Data d, Solution s, Parameter p) {
		Route emptyRoute;
		for (int i = 0; i < d.getVehicle(); i++) {
			emptyRoute = new Route();
			// emptyRoute.addCustomerbyName(d.getCustomerByName(0)); // depot am
			// anfang
			// einf���gen
			// emptyRoute.addCustomerbyNameSameCusotmerNextPosition(d
			// .getCustomerByName(0)); // depot am Ende einf���gen
			// ???????????
			emptyRoute.getRoute().put(emptyRoute.getRoute().size(),
					d.getCustomerByName(0).deepClone());
			emptyRoute.getRoute().put(emptyRoute.getRoute().size(),
					d.getCustomerByName(0).deepClone());
			s.getVehicleRoute().put(i, emptyRoute);
		}
		evalFunction(d, s, p);

		Map<Integer, Boolean> chosen = new HashMap<Integer, Boolean>();
		for (int i = 0; i < d.getCustomers().size(); i++) {
			chosen.put(i, false);
		}
		chosen.remove(0);
		chosen.put(0, true); // ���berschreiben oder nur anf���gen?

		double bestEval = 99999999;
		int bestCust = 0;
		int bestRoute = 0;
		int bestPlace = 0;

		for (int c = 1; c < d.getCustomers().size(); c++) {
			bestEval = 99999999;
			for (int k = 1; k < d.getCustomers().size(); k++) {
				if (!chosen.get(k)) {
					for (int i = 0; i < s.getVehicleRoute().size(); i++) {
						for (int j = 1; j < s.getVehicleRoute().get(i)
								.getRoute().size(); j++) {
							// System.out.println("Vehicle: "+ i +
							// " Customer zum einf���gen: "+ k +
							// " Postition des Customers in der Route: " + j +
							// " Size der Route vom Vehicle: " +
							// s.getVehicleRoute().get(i).getRoute().size());

							// Verschieben beim Einf���gen
							s.getVehicleRoute()
									.get(i)
									.insertIntoRouteCustomer(
											s.getVehicleRoute().get(i)
													.getRoute(), j, d.getCustomerByName(k).deepClone(), d, false);
							evalFunction(d, s, p);
							if (bestEval == 99999999) {
								bestEval = s.getEvalVal();
								bestCust = k;
								bestRoute = i;
								bestPlace = j;
							} else {
								if (s.getEvalVal() < bestEval) {
									bestEval = s.getEvalVal();
									bestCust = k;
									bestRoute = i;
									bestPlace = j;
								}
							}
							s.getVehicleRoute()
									.get(i)
									.eraseElementFromRouteCostumers(
											s.getVehicleRoute().get(i)
													.getRoute(), j, d);

						}
					}
				}
			}
			System.out.println("ist hier die endlosschleife?");
			s.getVehicleRoute()
					.get(bestRoute)
					.insertIntoRouteCustomer(
							s.getVehicleRoute().get(bestRoute).getRoute(),
							bestPlace, d.getCustomerByName(bestCust).deepClone(), d, true);
			chosen.remove(bestCust);
			chosen.put(bestCust, true); // ���berschreiben oder nur anf���gen?
			// System.out.println(s.printRoutes(d, s, p, ""));
		}// for inserting all customers except the depot
	}

	public void evalFunction(Data d, Solution s, Parameter p) {
		s.setEvalVal(0);
		s.setDistance(0);
		s.setTtt_of_route(0);
		s.setVio_of_dur(0);
		s.setVio_of_load(0);
		s.setVio_of_route(0);
		s.setWaitingTime(0);

		for (int i = 0; i < s.getVehicleRoute().size(); i++) {
			evalRoute(d, s.getVehicleRoute().get(i), p);
			s.setEvalVal(s.getEvalVal()
					+ s.getVehicleRoute().get(i).getEvalVal());
			s.setDistance(s.getDistance()
					+ s.getVehicleRoute().get(i).getDistance());
			s.setTtt_of_route(s.getTtt_of_route()
					+ s.getVehicleRoute().get(i).getTtt_of_route());
			s.setVio_of_dur(s.getVio_of_dur()
					+ s.getVehicleRoute().get(i).getVio_of_dur());
			s.setVio_of_load(s.getVio_of_load()
					+ s.getVehicleRoute().get(i).getVio_of_load());
			s.setVio_of_TW(s.getVio_of_TW()
					+ s.getVehicleRoute().get(i).getVio_of_TW());
			s.setWaitingTime(s.getWaitingTime()
					+ s.getVehicleRoute().get(i).getWaitingTime());
		}
	}

	public void evalRoute(Data d, Route r, Parameter p) {
		double dist = 0;
		double waiting = 0;
		double vioTW = 0;
		r.setDistance(0);
		r.setLoad(0);
		r.setTtt_of_route(0);
		r.setVio_of_TW(0);
		r.setWaitingTime(0);
		// update values
		for (int i = 0; i < r.getRoute().size() - 1; i++) {
			dist = d.getDistanceMatrix()[r.getRoute().get(i).getName()][r
					.getRoute().get(i + 1).getName()];
			r.setDistance(r.getDistance() + dist);
			r.setTtt_of_route(r.getTtt_of_route() + dist);
			if (i < r.getRoute().size() - 2) {
				waiting = Math.max(0.0,
						d.getCustomerByName(r.getRoute().get(i + 1).getName())
								.getReadyTime() - r.getTtt_of_route());
				r.setWaitingTime(r.getWaitingTime() + waiting);
				vioTW = Math.max(0.0, (r.getTtt_of_route() - d
						.getCustomerByName(r.getRoute().get(i + 1).getName())
						.getDueDate()));
				d.getCustomerByName(r.getRoute().get(i + 1).getName())
						.setVio_of_Tw(vioTW);
				r.setTtt_of_route(r.getTtt_of_route()
						+ (waiting + d.getCustomerByName(
								r.getRoute().get(i + 1).getName())
								.getServiceTime()));
				r.setVio_of_TW(r.getVio_of_TW() + vioTW);
				r.setLoad(r.getLoad()
						+ d.getCustomerByName(r.getRoute().get(i + 1).getName())
								.getDemand());
			} // end if
		}// end for

		r.setVio_of_load(Math.max(0, (r.getLoad() - d.getMaxQ())));
		r.setVio_of_dur(Math.max(0.0, (r.getTtt_of_route() - d
				.getCustomerByName(0).getDueDate())));
		r.setEvalVal(r.getDistance() + (p.getAlpha() * r.getVio_of_load())
				+ (p.getBeta() * r.getVio_of_dur())
				+ (p.getGamma() * r.getVio_of_TW()));

	}// evalRoute ende!!!

	public void twoOpt(Data d, Parameter p, Route vehicleroutes) {
		double bestTime = 0;
		double currTime = 0;
		Route help = new Route();
		boolean impr = true;
		int sequenzlength = Math.min(p.getSequenceLength_20pt(), vehicleroutes
				.getRoute().size() - 2);

		evalRoute(d, vehicleroutes, p);

		bestTime = vehicleroutes.getEvalVal();

		int cust = 0;
		boolean opt = false;

		if (vehicleroutes.getRoute().size() > 4) {
			while (impr) {
				System.out.println("while(impr) twoOpt");
				impr = false;
				for (int i = 0; i < vehicleroutes.getRoute().size() - 3
						&& !impr; i++) {

					System.out.println("for (int i = 0; i < vehicleroutes.getRoute().size() - 3 && !impr; i++)  twoOpt");
					for (int j = i + 1; j < 1 + Math.min(vehicleroutes
							.getRoute().size() - 1, i + 2 + sequenzlength); j++) {
						System.out.println("for (int j = i + 1; j < 1 + Math.min(vehicleroutes.getRoute().size() - 1, i + 2 + sequenzlength); j++)  twoOpt");
						opt = false;
						if (j == i + 1
								&& (vehicleroutes.getEvalVal() > vehicleroutes
										.getDistance() || (d
										.getDistanceMatrix()[0][vehicleroutes
										.getRoute().get(j + 1).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute()
												.get(vehicleroutes.getRoute()
														.size() - 2).getName()][vehicleroutes
												.getRoute().get(j).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(1).getName()][0] < d
										.getDistanceMatrix()[0][vehicleroutes
										.getRoute().get(1).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(j).getName()][vehicleroutes
												.getRoute().get(j + 1)
												.getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute()
												.get(vehicleroutes.getRoute()
														.size() - 2).getName()][0]))) {

							opt = true;
							help.getRoute().put(help.getRoute().size(),
									vehicleroutes.getRoute().get(0));
							for (int k = j + 1; k < vehicleroutes.getRoute()
									.size() - 1; k++) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}
							for (int k = j; k > 0; k--) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}
							help.getRoute().put(help.getRoute().size(),
									vehicleroutes.getRoute().get(0));

						}// if
						else if (j == Math.min(
								vehicleroutes.getRoute().size() - 1, i + 2
										+ sequenzlength)
								&& (vehicleroutes.getEvalVal() > vehicleroutes
										.getDistance() || (d
										.getDistanceMatrix()[0][vehicleroutes
										.getRoute()
										.get(vehicleroutes.getRoute().size() - 2)
										.getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(j - i - 1)
												.getName()][vehicleroutes
												.getRoute().get(1).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(j - i - 2)
												.getName()][0] < d
										.getDistanceMatrix()[0][vehicleroutes
										.getRoute().get(1).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(j - i - 2)
												.getName()][vehicleroutes
												.getRoute().get(j - i - 1)
												.getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute()
												.get(vehicleroutes.getRoute()
														.size() - 2).getName()][0]))) {
							opt = true;
							help.getRoute().put(help.getRoute().size(),
									vehicleroutes.getRoute().get(0));
							for (int k = vehicleroutes.getRoute().size() - 2; k > j
									- i - 2; k--) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}
							for (int k = 1; k < j - i - 1; k++) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}
							help.getRoute().put(help.getRoute().size(),
									vehicleroutes.getRoute().get(0));

						}// else if

						else if (j < Math.min(
								vehicleroutes.getRoute().size() - 1, i + 2
										+ sequenzlength)
								&& (vehicleroutes.getEvalVal() > vehicleroutes
										.getDistance() || (d
										.getDistanceMatrix()[vehicleroutes
										.getRoute().get(i).getName()][vehicleroutes
										.getRoute().get(j).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(i + 1)
												.getName()][vehicleroutes
												.getRoute().get(j + 1)
												.getName()] < d
										.getDistanceMatrix()[vehicleroutes
										.getRoute().get(i).getName()][vehicleroutes
										.getRoute().get(i + 1).getName()]
										+ d.getDistanceMatrix()[vehicleroutes
												.getRoute().get(j).getName()][vehicleroutes
												.getRoute().get(j + 1)
												.getName()]))) {
							opt = true;
							for (int k = 0; k < i + 1; k++) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}
							for (int k = j; k > i; k--) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}
							for (int k = j + 1; k < vehicleroutes.getRoute()
									.size(); k++) {
								help.getRoute().put(help.getRoute().size(),
										vehicleroutes.getRoute().get(k));
							}

						}// else if

						if (opt) {
							if (help.getRoute().get(0).getName() != 0
									&& help.getRoute()
											.get(help.getRoute().size() - 1)
											.getName() == 0) {
								do {

									cust = help.getRoute().get(0).getName();
									if (cust < 0
											|| cust > d.getCustomers().size()) {
										System.out
												.println("2-opt_full: cust ist falsch");
									}
									help.insertIntoRouteCustomer(help
											.getRoute(), 0 + help.getRoute()
											.size() - 1, d.getCustomerByName(cust), d, true);// deepclone removed
									help.eraseElementFromRouteCostumers(
											help.getRoute(), 0, d);

								} while (help.getRoute().get(0).getName() != 0);
							} else if (help.getRoute().get(0).getName() == 0
									&& help.getRoute()
											.get(help.getRoute().size() - 1)
											.getName() != 0) {
								do {

									if (cust < 0
											|| cust > d.getCustomers().size()) {
										System.out
												.println("2-opt_full: cust ist falsch");
									}
									cust = help.getRoute()
											.get(help.getRoute().size() - 1)
											.getName();
									
									help.insertIntoRouteCustomer(
											help.getRoute(), 1, d.getCustomerByName(cust).deepClone(), d, true);//deepclone removed
									help.eraseElementFromRouteCostumers(help.getRoute(), 1, d); // Endlosschleife gefixed!!!

								} while (help.getRoute()
										.get(help.getRoute().size() - 1)
										.getName() != 0);
							}// elseif

							if (help.getRoute().get(0).getName() != 0
									|| help.getRoute()
											.get(help.getRoute().size() - 1)
											.getName() != 0) {
								for (int f = 0; f < vehicleroutes.getRoute()
										.size(); f++) {
									System.out.print(vehicleroutes.getRoute()
											.get(f).getName()
											+ " ");
								}// for

								System.out.println();
								for (int f = 0; f < help.getRoute().size(); f++) {
									System.out.print(help.getRoute().get(f)
											.getName()
											+ " ");
								}
								System.out.println();
								System.out.println();

							}// if

							if (help.getRoute().size() != vehicleroutes
									.getRoute().size()) {
								System.out
										.println("Two-opt_full: help.getRoute().size()!=vehicleroutes.getRoute().size()");
							}// if

							evalRoute(d, help, p);
							currTime = help.getEvalVal();

							if (bestTime - currTime > 0) {
								bestTime = currTime;
								vehicleroutes = help;
								impr = true;
								d.setFirst_Impr(true);
							}// if

							help = new Route();

						}

					}
				}
			}
		} else if (vehicleroutes.getRoute().size() == 4) {
			help = new Route();
			help.getRoute().put(help.getRoute().size(),
					vehicleroutes.getRoute().get(0));
			help.getRoute().put(help.getRoute().size(),
					vehicleroutes.getRoute().get(2));
			help.getRoute().put(help.getRoute().size(),
					vehicleroutes.getRoute().get(1));
			help.getRoute().put(help.getRoute().size(),
					vehicleroutes.getRoute().get(3));
			evalRoute(d, help, p);
			if (bestTime - currTime > 0) {
				vehicleroutes = help;
			}
			help = new Route();

		}// elseif
		else
			evalRoute(d, vehicleroutes, p);

	}// TwoOpt

	public void crossMove(Data d, Parameter p, Route r1, Route r2) { // first
																		// improvement
		double bestEval, currEval = 0;
		Route help1 = new Route();
		Route help2 = new Route();
		boolean impr = true;
		int sequenzlength = p.getSequenceLength_crossMove();

		evalRoute(d, r1, p);
		evalRoute(d, r2, p);
		bestEval = r1.getEvalVal() + r2.getEvalVal();

		int help_i, help_j = 0;

		while (impr) {
			impr = false;
			for (int s = 0; s < Math.min(r1.getRoute().size() - 2,
					sequenzlength) && !impr; s++) {
				for (int t = 0; t < Math.min(r2.getRoute().size() - 2,
						sequenzlength) && !impr; t++) {
					if (s > 0 || t > 0) {
						for (int i = 1; i < r1.getRoute().size() - 1 && !impr; i++) {
							for (int j = 1; j < r2.getRoute().size() - 1
									&& !impr; j++) {
								help_i = i + s;
								help_j = j + t;
								if (help_i >= r1.getRoute().size()) {
									help_i = help_i
											- (r1.getRoute().size() - 2);
								}
								if (help_j >= r2.getRoute().size()) {
									help_j = help_j
											- (r2.getRoute().size() - 2);
								}

								/*
								 * //zum testen
								 * System.out.println("CrossMove: help_i: " +
								 * help_i + " help_j: " + help_j); if(help_j <
								 * 0){ System.out.println("CrossMove: help_i: "
								 * + help_i + " help_j: " + help_j); }
								 */

								if (r1.getEvalVal() + r2.getEvalVal() > r1
										.getDistance() + r2.getDistance()
										|| (d.getDistanceMatrix()[r1.getRoute()
												.get(i - 1).getName()][r2
												.getRoute().get(j).getName()]
												+ d.getDistanceMatrix()[r2
														.getRoute().get(j - 1)
														.getName()][r1
														.getRoute().get(i)
														.getName()]
												+ d.getDistanceMatrix()[r1
														.getRoute()
														.get(help_i - 1)
														.getName()][r2
														.getRoute().get(help_j)
														.getName()]
												+ d.getDistanceMatrix()[r2
														.getRoute()
														.get(help_j - 1)
														.getName()][r1
														.getRoute().get(help_i)
														.getName()] < d
												.getDistanceMatrix()[r1
												.getRoute().get(i - 1)
												.getName()][r1.getRoute()
												.get(i).getName()]
												+ d.getDistanceMatrix()[r2
														.getRoute().get(j - 1)
														.getName()][r2
														.getRoute().get(j)
														.getName()]
												+ d.getDistanceMatrix()[r1
														.getRoute()
														.get(help_i - 1)
														.getName()][r1
														.getRoute().get(help_i)
														.getName()]
												+ d.getDistanceMatrix()[r2
														.getRoute()
														.get(help_j - 1)
														.getName()][r2
														.getRoute().get(help_j)
														.getName()])) {
									// help1
									for (int l = 0; l < i; l++) {
										help1.getRoute().put(
												help1.getRoute().size(),
												r1.getRoute().get(l));

									}// for

									for (int l = 0; l < t; l++) {
										if (j + l < r2.getRoute().size() - 1) {
											help1.getRoute().put(
													help1.getRoute().size(),
													r2.getRoute().get(j + l));

										} else {
											help1.getRoute()
													.put(help1.getRoute()
															.size(),
															r2.getRoute()
																	.get(j
																			+ l
																			- r2.getRoute()
																					.size()
																			+ 2));
										}// if

									}// for

									if (i + s < r1.getRoute().size()) {
										for (int l = i + s; l < r1.getRoute()
												.size(); l++) {
											help1.getRoute().put(
													help1.getRoute().size(),
													r1.getRoute().get(l));
										}
									} else {
										for (int l = 0; l < s
												- r1.getRoute().size() + 1 + i; l++) {
											help1.eraseElementFromRouteCostumers(
													help1.getRoute(), 1, d);
										}
										help1.getRoute().put(
												help1.getRoute().size(),
												r1.getRoute().get(0));
									}

									// help2
									for (int l = 0; l < j; l++) {
										help2.getRoute().put(
												help2.getRoute().size(),
												r2.getRoute().get(l));

									}// for

									for (int l = 0; l < s; l++) {
										if (i + l < r1.getRoute().size() - 1) {
											help2.getRoute().put(
													help2.getRoute().size(),
													r1.getRoute().get(i + l));

										} else {
											help2.getRoute()
													.put(help2.getRoute()
															.size(),
															r1.getRoute()
																	.get(i
																			+ l
																			- r1.getRoute()
																					.size()
																			+ 2));
										}// if

									}// for

									if (j + t < r2.getRoute().size()) {
										for (int l = j + t; l < r2.getRoute()
												.size(); l++) {
											help2.getRoute().put(
													help2.getRoute().size(),
													r2.getRoute().get(l));
										}
									} else {
										for (int l = 0; l < t
												- r2.getRoute().size() + 1 + j; l++) {
											help2.eraseElementFromRouteCostumers(
													help2.getRoute(), 1, d);
										}
										help2.getRoute().put(
												help2.getRoute().size(),
												r2.getRoute().get(0));
									}

									evalRoute(d, help1, p);
									evalRoute(d, help2, p);
									currEval = help1.getEvalVal()
											+ help2.getEvalVal();
									if (bestEval - currEval > 0) {
										bestEval = currEval;
										r1 = help1;
										r2 = help2;
										impr = true;
										d.setFirst_Impr(true);

									}

									help1 = new Route();
									help2 = new Route();

								}

							}// for j
						}// for i
					}// if s,t
				}// for t
			}// for s

		}// while impr

	}// crossmove

	public void orOpt(Data d, Parameter p, Route r) {
		double bestTime, currTime = 0;
		Route help = new Route();
		boolean impr = true;
		int sequenzlength = Math.min(p.getSequenceLength_orOpt(), r.getRoute()
				.size() - 2);

		evalRoute(d, r, p);

		bestTime = r.getEvalVal();
		boolean opt = false;

		if (r.getRoute().size() > 4) {
			while (impr) {
				impr = false;
				for (int k = 1; k <= sequenzlength && !impr; k++) {
					for (int j = 0; j < r.getRoute().size() - k + 1 && !impr; j++) {
						for (int i = 1; i < r.getRoute().size() && !impr; i++) {
							if (i < j || i > j + k - 1) {
								opt = false;
								// start cust = i-1

								if (i < j
										&& j < r.getRoute().size() - k
										&& (r.getEvalVal() > r.getDistance() || d
												.getDistanceMatrix()[r
												.getRoute().get(i - 1)
												.getName()][r.getRoute().get(j)
												.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute()
														.get(j + k - 1)
														.getName()][r
														.getRoute().get(i)
														.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute().get(j - 1)
														.getName()][r
														.getRoute().get(j + k)
														.getName()] < d
												.getDistanceMatrix()[r
												.getRoute().get(i - 1)
												.getName()][r.getRoute().get(i)
												.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute().get(j - 1)
														.getName()][r
														.getRoute().get(j)
														.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute()
														.get(j + k - 1)
														.getName()][r
														.getRoute().get(j + k)
														.getName()])) {

									opt = true;
									for (int l = 0; l < i; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = j; l < j + k; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = i; l < j; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = j + k; l < r.getRoute().size(); l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}

								}// if
								else if (i < j
										&& j == r.getRoute().size() - k + 1
										&& (r.getEvalVal() > r.getDistance() || (d
												.getDistanceMatrix()[r
												.getRoute().get(i - 1)
												.getName()][r.getRoute().get(j)
												.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute()
														.get(j + k - 1)
														.getName()][r
														.getRoute().get(i)
														.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute().get(j - 1)
														.getName()][r
														.getRoute().get(j + k)
														.getName()] < d
												.getDistanceMatrix()[r
												.getRoute().get(i - 1)
												.getName()][r.getRoute().get(i)
												.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute().get(j - 1)
														.getName()][r
														.getRoute().get(j)
														.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute()
														.get(j + k - 1)
														.getName()][r
														.getRoute().get(j + k)
														.getName()]))) {

									opt = true;
									for (int l = 0; l < i; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = j; l < j + k; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = i; l < j; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = j + k; l < r.getRoute().size(); l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
								}// else if
								else if (i > j + k - 1
										&& j < 0
										&& (r.getEvalVal() > r.getDistance() || (d
												.getDistanceMatrix()[r
												.getRoute().get(j - 1)
												.getName()][r.getRoute()
												.get(j + k).getName()]
												+ d.getDistanceMatrix()[r
														.getRoute().get(i - 1)
														.getName()][r
														.getRoute().get(j)
														.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute()
														.get(j + k - 1)
														.getName()][r
														.getRoute().get(i)
														.getName()] < d
												.getDistanceMatrix()[r
												.getRoute().get(i - 1)
												.getName()][r.getRoute().get(i)
												.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute().get(j - 1)
														.getName()][r
														.getRoute().get(j)
														.getName()]
												+ d.getDistanceMatrix()[r
														.getRoute()
														.get(j + k - 1)
														.getName()][r
														.getRoute().get(j + k)
														.getName()]))) {

									opt = true;
									for (int l = 0; l < j; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = j + k; l < i; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = j; l < j + k; l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
									for (int l = i; l < r.getRoute().size(); l++) {
										help.getRoute().put(
												help.getRoute().size(),
												r.getRoute().get(l));
									}
								}// else if

								if (opt) {
									evalRoute(d, help, p);
									currTime = help.getEvalVal();
									if (bestTime - currTime > 0) {
										bestTime = currTime;
										r = help;
										impr = true;
										d.setFirst_Impr(true);
									}// if

									help = new Route();

								}// if

							}
						}
					}
				}

			}

		}// if r.getroute.size >4

		else if (r.getRoute().size() == 4) {
			help = new Route();
			help.getRoute().put(help.getRoute().size(), r.getRoute().get(0));
			help.getRoute().put(help.getRoute().size(), r.getRoute().get(2));
			help.getRoute().put(help.getRoute().size(), r.getRoute().get(1));
			help.getRoute().put(help.getRoute().size(), r.getRoute().get(3));
			evalRoute(d, help, p);
			currTime = help.getEvalVal();
			if (bestTime - currTime > 0) {
				r = help;
			}
			help = new Route();

		} else {
			evalRoute(d, r, p);
		}

	}// orOpt

	public void twoOptStar_Cross(Data d, Parameter p, Route r1, Route r2) {
		double bestEval, currEval = 0;
		Route help1 = new Route();
		Route help2 = new Route();
		boolean impr = true;

		evalRoute(d, r1, p);
		evalRoute(d, r2, p);

		bestEval = r1.getEvalVal() + r2.getEvalVal();
		for (int o = 0; o < help1.getRoute().size(); o++) {
			help1.getRoute().remove(o);
		}
		for (int o = 0; o < help2.getRoute().size(); o++) {
			help2.getRoute().remove(o);
		}// unn��tig?

		while (impr) {
			impr = false;
			for (int i = 2; i < r1.getRoute().size() - 1 && !impr; i++) {
				for (int j = 2; j < r2.getRoute().size() - 1 && !impr; j++) {
					if (i < r1.getRoute().size() - 3
							|| j < r2.getRoute().size() - 3) {
						if ((r1.getEvalVal() + r2.getEvalVal() > r1
								.getDistance() + r2.getDistance())
								|| (d.getDistanceMatrix()[r1.getRoute()
										.get(i - 1).getName()][r2.getRoute()
										.get(j).getName()]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(j - 1).getName()][r1
												.getRoute().get(i).getName()] < d
										.getDistanceMatrix()[r1.getRoute()
										.get(i - 1).getName()][r1.getRoute()
										.get(i).getName()]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(j - 1).getName()][r2
												.getRoute().get(j).getName()])) {
							// help1
							for (int l = 0; l < i; l++) {
								help1.getRoute().put(help1.getRoute().size(),
										r1.getRoute().get(l));
							}
							for (int l = j; l < r2.getRoute().size(); l++) {
								help1.getRoute().put(help1.getRoute().size(),
										r2.getRoute().get(l));
							}

							// help2
							for (int l = 0; l < j; l++) {
								help2.getRoute().put(help2.getRoute().size(),
										r2.getRoute().get(l));
							}
							for (int l = i; l < r1.getRoute().size(); l++) {
								help1.getRoute().put(help2.getRoute().size(),
										r1.getRoute().get(l));
							}

							evalRoute(d, help1, p);
							evalRoute(d, help2, p);

							currEval = help1.getEvalVal() + help2.getEvalVal();

							if (bestEval - currEval > 0) {
								bestEval = currEval;
								r1 = help1;
								r2 = help2;
								impr = true;
								d.setFirst_Impr(true);

							}
							help1 = new Route();
							help2 = new Route();

						}

						if (!d.isFirst_Impr()
								&& ((r1.getEvalVal() + r2.getEvalVal() > r1
										.getDistance() + r2.getDistance()) || (d
										.getDistanceMatrix()[r1.getRoute()
										.get(i - 1).getName()][r2.getRoute()
										.get(j).getName()]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(j - 1).getName()][r1
												.getRoute().get(i).getName()]
										+ d.getDistanceMatrix()[r1.getRoute()
												.get(i).getName()][0]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(j).getName()][0] < d
										.getDistanceMatrix()[r1.getRoute()
										.get(i - 1).getName()][r1.getRoute()
										.get(i).getName()]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(j - 1).getName()][r2
												.getRoute().get(j).getName()]
										+ d.getDistanceMatrix()[r1.getRoute()
												.get(r1.getRoute().size() - 2)
												.getName()][0]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(r2.getRoute().size() - 2)
												.getName()][0]))) {
							// help1
							for (int l = 0; l < i; l++) {
								help1.getRoute().put(help1.getRoute().size(),
										r1.getRoute().get(l));
							}
							for (int l = r2.getRoute().size() - 1; l > j; l--) {
								help1.getRoute().put(help1.getRoute().size(),
										r2.getRoute().get(l - 1));
							}
							help1.getRoute().put(help1.getRoute().size(),
									r2.getRoute().get(0));

							// help2
							for (int l = 0; l < j; l++) {
								help2.getRoute().put(help2.getRoute().size(),
										r2.getRoute().get(l));
							}
							for (int l = r1.getRoute().size() - 1; l > i; l--) {
								help2.getRoute().put(help2.getRoute().size(),
										r1.getRoute().get(l - 1));
							}
							help2.getRoute().put(help2.getRoute().size(),
									r1.getRoute().get(0));

							evalRoute(d, help1, p);
							evalRoute(d, help2, p);

							currEval = help1.getEvalVal() + help2.getEvalVal();

							if (bestEval - currEval > 0) {
								bestEval = currEval;
								r1 = help1;
								r2 = help2;
								impr = true;
								d.setFirst_Impr(true);
							}
							help1 = new Route();
							help2 = new Route();

						}// if

						if (!d.isFirst_Impr()
								&& ((r1.getEvalVal() + r2.getEvalVal() > r1
										.getDistance() + r2.getDistance()) || (d
										.getDistanceMatrix()[r1.getRoute()
										.get(i - 1).getName()][r1.getRoute()
										.get(r1.getRoute().size() - 2)
										.getName()]
										+ d.getDistanceMatrix()[r1.getRoute()
												.get(i).getName()][0] < d
										.getDistanceMatrix()[r1.getRoute()
										.get(i - 1).getName()][r1.getRoute()
										.get(i).getName()]
										+ d.getDistanceMatrix()[r1.getRoute()
												.get(r1.getRoute().size() - 2)
												.getName()][0]))) {
							// help1
							for (int l = 0; l < i; l++) {
								help1.getRoute().put(help1.getRoute().size(),
										r1.getRoute().get(l));
							}
							for (int l = r1.getRoute().size() - 1; l > i; l--) {
								help1.getRoute().put(help1.getRoute().size(),
										r1.getRoute().get(l - 1));
							}
							help1.getRoute().put(help1.getRoute().size(),
									r1.getRoute().get(0));

							// help2
							for (int l = 0; l < r2.getRoute().size(); l++) {
								help2.getRoute().put(help2.getRoute().size(),
										r2.getRoute().get(l));
							}

							evalRoute(d, help1, p);
							evalRoute(d, help2, p);

							currEval = help1.getEvalVal() + help2.getEvalVal();

							if (bestEval - currEval > 0) {
								bestEval = currEval;
								r1 = help1;
								r2 = help2;
								impr = true;
								d.setFirst_Impr(true);
							}
							help1 = new Route();
							help2 = new Route();

						}// if

						if (!d.isFirst_Impr()
								&& ((r1.getEvalVal() + r2.getEvalVal() > r1
										.getDistance() + r2.getDistance()) || (d
										.getDistanceMatrix()[r2.getRoute()
										.get(j - 1).getName()][r2.getRoute()
										.size() - 2]
										+ d.getDistanceMatrix()[r2.getRoute()
												.get(j).getName()][0] < d
										.getDistanceMatrix()[r2.getRoute()
										.get(j - 1).getName()][r2.getRoute()
										.get(j).getName()]
										+ d.getDistanceMatrix()[r2.getRoute()
												.size() - 2][0]))) {
							// if correct? r2.getroute.size-2

							// help1

							for (int l = 0; l < r1.getRoute().size(); l++) {
								help1.getRoute().put(help1.getRoute().size(),
										r1.getRoute().get(l));
							}

							// help2
							for (int l = 0; l < j; l++) {
								help2.getRoute().put(help2.getRoute().size(),
										r2.getRoute().get(l));
							}
							for (int l = r2.getRoute().size() - 1; l > j; l--) {
								help2.getRoute().put(help2.getRoute().size(),
										r2.getRoute().get(l - 1));
							}
							help2.getRoute().put(help2.getRoute().size(),
									r2.getRoute().get(0));

							evalRoute(d, help1, p);
							evalRoute(d, help2, p);

							currEval = help1.getEvalVal() + help2.getEvalVal();

							if (bestEval - currEval > 0) {
								bestEval = currEval;
								r1 = help1;
								r2 = help2;
								impr = true;
								d.setFirst_Impr(true);
							}
							help1 = new Route();
							help2 = new Route();

						}// if
					}

				}
			}
		}// twoOptStar_cross

	}
	
	public void moveOrNot(Data d, Shaking shakingset, Parameter p, Solution s, Solution bs){
		double newEvalval = 0, oldEvalval = 0;
		for(int i = 0; i < shakingset.getShaked().size(); i++){
			if(shakingset.getShaked().get(i)){
				newEvalval += shakingset.getShakedRoutes().get(i).getEvalVal();
				oldEvalval += s.getVehicleRoute().get(i).getEvalVal();
			}
		}
		if((newEvalval<oldEvalval) || ((newEvalval/oldEvalval) < 1.25 && (d.getSteps()%d.getDegradation()==0))){
			for(int i = 0; i < shakingset.getShaked().size(); i++){
				if(shakingset.getShaked().get(i)){
					updateValues(s, s.getVehicleRoute().get(i), shakingset.getShakedRoutes().get(i));
					s.getVehicleRoute().remove(i);
					s.getVehicleRoute().put(i, shakingset.getShakedRoutes().get(i));
					
				}
			}
			System.out.println("MoveOrNot: " + s.getEvalVal() + " < " + (bs.getEvalVal()-0.000000001));
			if(s.getEvalVal()<bs.getEvalVal()-0.000000001){
				bs = s.deepClone();
				System.out.println("New solution!");
				System.out.println("Total Distance = " + s.getDistance());
				System.out.println("Violation TW = " + s.getVio_of_TW());
				System.out.println("Violation Ld = " + s.getVio_of_load());
				System.out.println("Violation RL = "+ s.getVio_of_dur());
				System.out.println("Waiting Time = " + s.getWaitingTime());
				System.out.println("Objective Value = "+ s.getDistance()+s.getVio_of_TW());
				System.out.println("Evaluation Value = "+s.getEvalVal());
				System.out.println("Number of routes = "+ s.getVehicleRoute().size());
				
				d.setImprove(0);
				shakingset.setNumber_shaking(1);
				shakingset.setCount_shaking(3);
				
				if(p.getGamma() > 50 && p.getGamma() < 900 && bs.getVio_of_TW() < 0.000000001){
					p.setGamma(10000);
					}
				
			}//if
			shakingset.setKappa(shakingset.getKappaStart());
			d.setSteps(0);
			
		}else{
			shakingset.setKappa(shakingset.getKappa()%shakingset.getKappaEnd());
			shakingset.setKappa(shakingset.getKappa()+1);
		}
		d.setSteps(d.getSteps()+1);
		d.setImprove(d.getImprove()+1);
		
		
	}//moveOrNot

	public Route getEmptyRoute() {
		return emptyRoute;
	}

	public void setEmptyRoute(Route emptyRoute) {
		this.emptyRoute = emptyRoute;
	}

	public boolean[] getChoosen() {
		return choosen;
	}

	public void setChoosen(boolean[] choosen) {
		this.choosen = choosen;
	}

	public void updateValues(Solution s, Route r, Route p){
		s.setEvalVal(s.getEvalVal()+p.getEvalVal()-r.getEvalVal());
		s.setDistance(s.getDistance()+p.getDistance()-r.getDistance());
		s.setTtt_of_route(s.getTtt_of_route()+p.getTtt_of_route()-r.getTtt_of_route());
		s.setVio_of_dur(s.getVio_of_dur()+p.getVio_of_dur()-r.getVio_of_dur());
		s.setVio_of_load(s.getVio_of_load()+p.getVio_of_load()-r.getVio_of_load());
		s.setVio_of_TW(s.getVio_of_TW()+p.getVio_of_TW()-r.getVio_of_TW());
		s.setWaitingTime(s.getWaitingTime()+p.getWaitingTime()-r.getWaitingTime());
		
	}
	
	
}
